Wireless networks have experienced increased development in the past decade. Two types of wireless networks are infra-structured wireless networks, and ad hoc wireless networks.
An infra-structured wireless network typically includes a communication network with fixed and wired gateways. Many infra-structured wireless networks employ a mobile unit or host which communicates with a fixed base station that is coupled to a wired network. The mobile unit can move geographically while it is communicating over a wireless link to the base station. When the mobile unit moves out of range of one base station, it connects or “handsover” to a new base station and starts communicating with the wired network through the new base station.
The wired network typically has a billing manager, such as an authentication, authorization, and accounting (AAA) center, which monitors packet traffic to and from each wireless device. The AAA center provides a framework for intelligently controlling access to communication resources, enforces policies, audits usage, and provides the information necessary to bill for services. The accounting aspect of the AAA center measures the resources a user consumes during access. This can include the amount of system time or the amount of data a user has sent and/or received during a session. Accounting is carried out by logging of session statistics and usage information and is used for authorization control, billing, trend analysis, resource utilization, and capacity planning activities. Among other functions, the AAA center can maintain a count of packets transmitted by a wireless device and then charge the user of the wireless device for use of the network based on the number of packets transmitted.
In comparison to infra-structured wireless networks, such as cellular networks or satellite networks, ad hoc networks are self-forming networks which can operate in the absence of any fixed infrastructure, and in some cases the ad hoc network is formed entirely of mobile nodes (e.g., a peer-to-peer ad hoc network). An ad hoc network typically includes a number of geographically-distributed, potentially mobile units, sometimes referred to as “nodes,” which are wirelessly connected to each other by one or more links (e.g., radio frequency communication channels). The nodes can communicate with each other over a wireless media without the support of an infra-structured or wired network. Ad hoc networks can also be self-healing. Links or connections between these nodes can change dynamically in an arbitrary manner as existing nodes move within the ad hoc network, as new nodes join or enter the ad hoc network, or as existing nodes leave or exit the ad hoc network. Because the topology of an ad hoc network can change significantly techniques are needed which can allow the ad hoc network to dynamically adjust to these changes. Due to the lack of a fixed infrastructure (e.g., a central controller), many network-controlling functions can be distributed among the nodes such that the nodes can self-organize and reconfigure in response to topology changes.
One characteristic of the nodes is that their transmission range is usually relatively limited in comparison to cellular networks. Each node can typically communicate over a short range with nodes which are a single “hop” away. Such nodes are sometimes referred to as “neighbor nodes.” Because ad hoc networks lack infrastructure, each node in an ad hoc network relies on other nodes in the network to help to forward/route/relay its packets (e.g., data and control information) throughout the network until the packets reach their intended destination. For example, when a node transmits packets to a destination node and the nodes are separated by more than one hop (e.g., the distance between two nodes exceeds the radio transmission range of the nodes, or a physical barrier is present between the nodes), the packets can be relayed via intermediate nodes (“hop-by-hop”) until the packets reach the destination node. Each intermediate node acts as a router which can intelligently route the packets (e.g., data and control information) to another node until the packets eventually reach their final destination. For instance, if the destination is a user connected to the Internet, packets sent from a source node to that user will “hop” or be routed by intermediate nodes until they reach a cellular base station, a WLAN AP or other gateway to the Internet.
To assist with relaying of packets, each node maintains routes or routing information to other nodes in the network and can utilize routing techniques to adapt to changes in the interconnectivity between nodes. The nodes can maintain this routing information by performing periodic link and topology updates. In this context it is desirable to provide techniques which maximize the robustness of the routing topology for the maximum period of time to enable uninterrupted communication.
When a node routes a packet sent from another node, this routing consumes the bandwidth and battery resources of the node which performs the routing function. Published U.S. Patent Application US20050165696A1, entitled “Micro-Payment Scheme Encouraging Collaboration In Multi-Hop Cellular Networks,” and an article by L. Buttyan et al., “Stimulating Cooperation in Self-Organizing Mobile Ad Hoc Networks,” ACM Journal for Mobile Networks (MONET), special issue on Mobile Ad Hoc Networks, October 2003, Vol. 8, No. 5, propose micro payment and bit credit/debit schemes that provide accounting techniques for packet routing. According to these techniques, a billing system, in the cellular core (wired) network, uses credits/debits to account for packets routed by a particular node for other nodes in its ad hoc network. However, these credits/debits provide little or no incentive to the owner of a particular node to route traffic (e.g., packets) to/from another node within their ad hoc network.
Notwithstanding these advances, techniques are needed to encourage nodes to perform a routing function to assist other nodes in routing packets throughout an ad hoc network. It would be desirable to provide techniques which can provide an incentive for nodes to route packets for other nodes.
Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of embodiments of the present invention.